/*
提交链接:https://leetcode.cn/problems/numbers-with-repeated-digits/description/
1012. 至少有 1 位重复的数字
赖德檀 2024/10/5
*/

class Solution {
public:
    int f(vector<int>& cnt,int n,int len,int k,int start)
    {
        if(len==0) return 1;
        int ans = 0;
        int sum = (n/k)%10;
        for(int i=0;i<sum;i++)
        {
            if((start & (1<<i))==0)
            ans += cnt[len-1];
        }
        if((start & (1<<sum))==0)
        ans += f(cnt,n,len-1,k/10,start|(1<<sum));
        return ans;
    }
    int numDupDigitsAtMostN(int n) {
        int t=n/10;
        int len=1;
        int k=1;
        int start=0;
        int ans=0;
        while(t>0)
        {
            len++;
            k*=10;
            t/=10;
        }
        vector<int>cnt(len,0);
        cnt[0]=1;
        for(int i=1,x=10-len+1;i<len;x++,i++)
        {
            cnt[i]=cnt[i-1]*x;
        }
        if(len>=2)
        {
            ans=9;
            for(int i=2,a=9,b=9;i<len;i++,b--)
            {
                a*=b;
                ans+=a;
            }
        }
        int sum = n/k;
        ans += cnt[len-1]*(sum-1);
        ans += f(cnt,n,len-1,k/10,start|(1<<sum));
        return n-ans;
    }
};